W3. Разделяй и властвуй (divide and conquer), master theorem, эффективная сортировка

Автор

Nikolai Kudasov

Дата публикации

2 февраля 2026 г.

1. Краткое содержание

1.1 Введение в divide and conquer

Divide and conquer — базовый приём проектирования алгоритмов: задача разбивается на меньшие независимые подзадачи того же типа, каждая решается отдельно, затем ответы combine в ответ исходной задачи. Особенно силён там, где декомпозиция естественна.

Стратегия по сути рекурсивна: каждый вызов решает меньший экземпляр до base case (подзадача уже «маленькая»), после чего при раскрутке стека результаты объединяются.

1.1.1 Три части divide and conquer

У любого такого алгоритма три компонента:

Divide: разбить задачу на подзадачи того же типа, обычно уменьшив размер входа (например, разрезать массив пополам или снизить степень в exponentiation).
Conquer: решить каждую подзадачу рекурсивно. Base case задаёт порог, когда рекурсия не нужна (массив из одного элемента уже «отсортирован»).
Combine: слить решения подзадач в решение исходной задачи. Этот шаг должен быть дёшев: иначе он доминирует во времени.

Наглядно: большая библиотека — не сортировать всё сразу, а разбить на отсеки, отсортировать каждый (conquer), затем слить отсортированные части (combine). Слияние двух уже отсортированных списков существенно проще, чем сортировать один несортированный.

1.2 Анализ divide and conquer: рекуррентности

Время естественно записывается рекуррентностью (recurrence relation) — уравнением на $T(n)$ через время на меньших размерах.

Типичный вид: \[T(n) = \begin{cases} \Theta(1) & \text{if } n \le n_0 \text{ (base case)} \\ a \cdot T(n/b) + f(n) & \text{otherwise (recursive case)} \end{cases}\]

$a$: число подзадач на шаге divide
$n/b$: размер каждой подзадачи (вход делится на $b$)
$f(n)$: время на divide и combine без учёта рекурсивных вызовов

Пример: у merge sort $a=2$, размеры $n/b=n/2$, слияние $f(n)=\Theta(n)$: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Умение решать рекуррентности даёт асимптотику всего алгоритма.

1.2.1 Способы решения рекуррентностей

Три основных подхода:

Substitution method: угадать границу и доказать индукцией; нужна интуиция.
Recursion tree method: дерево рекурсии, сумма работы по уровням, геометрические ряды; показывает, где «тратится» время.
Master method: рецепт для $T(n)=aT(n/b)+f(n)$; на практике чаще всего достаточно выписать $a$, $b$, $f(n)$.

1.3 Master theorem

Master theorem (Cormen et al., Theorem 4.1) даёт готовый ответ для \[T(n) = a \cdot T(n/b) + f(n)\] при $a\ge 1$, $b>1$ и асимптотически неотрицательном $f(n)$. Сравнивают рост $f(n)$ (стоимость divide/combine) с $n^{\log_b a}$ (совокупная «масса» рекурсивных вызовов).

1.3.1 Три случая

Case 1 — доминирует рекурсия: если $f(n)$ существенно меньше $n^{\log_b a}$, время задаёт рекурсия.

\[\text{If } \exists\, \epsilon > 0 \text{ such that } f(n) = O(n^{\log_b a - \epsilon}), \text{ then } T(n) = \Theta(n^{\log_b a})\]

Смысл: основная работа на листьях дерева рекурсии; листьев $\Theta(n^{\log_b a})$, на листе $\Theta(1)$.

Case 2 — баланс: если $f(n)$ того же порядка, что $n^{\log_b a}$ (с возможными логарифмическими множителями), вклад «по уровням» сопоставим.

\[\text{If } \exists\, k \ge 0 \text{ such that } f(n) = \Theta(n^{\log_b a} \log^k n), \text{ then } T(n) = \Theta(n^{\log_b a} \log^{k+1} n)\]

Смысл: работа распределена по уровням; число уровней $\Theta(\log_b n)$; логарифмические факторы в $f(n)$ накапливаются.

Case 3 — доминирует combine: если $f(n)$ существенно больше $n^{\log_b a}$, главный вклад даёт divide/combine.

\[\text{If } \exists\, \epsilon > 0 \text{ such that } f(n) = \Omega(n^{\log_b a + \epsilon}), \text{ and the **regularity condition** } af(n/b) \le c \cdot f(n)\] \[\text{holds for some } c < 1 \text{ and all sufficiently large } n, \text{ then } T(n) = \Theta(f(n))\]

Смысл: верхний уровень рекурсии тянет основное время; regularity condition не даёт стоимости combine «взрываться» при подъёме по дереву.

Что такое regularity condition? После divide и combine на уровне $i$ работа не должна сильно превосходить уровень $i-1$ — тогда ряд стоимостей ведёт себя как сходящийся геометрический ряд, и суммарно доминирует верх.

1.3.2 Смысл $n^{\log_b a}$

Это «чистая» стоимость рекурсии — суммарная работа всех рекурсивных вызовов без учёта divide/combine:

на уровне 1 — $a$ подзадач размера $n/b$, вклад $a\cdot T(n/b)$;
на уровне 0 (корень) — одна задача размера $n$;
на уровне $k$ — $a^k$ задач размера $n/b^k$;
глубина $\log_b n$;
число листьев: $a^{\log_b n}=n^{\log_b a}$.

1.4 Задача о максимальном подмассиве (Maximum Subarray Problem)

Maximum Subarray Problem — классический пример задачи, к которой естественно применим divide and conquer, и наглядно показывающий, как этот приём улучшает наивные алгоритмы.

1.4.1 Постановка задачи

Вход: последовательность из $n$ чисел $\langle a_1, a_2, \dots, a_n \rangle$.

Выход: индексы $l$ и $r$ такие, что $\sum_{i=l}^{r} a_i \ge \sum_{i=l'}^{r'} a_i$ для любых $1 \le l' \le r' \le n$. Нужно найти непрерывный подмассив с максимальной суммой.

Практика: задача часто встречается в финансовом анализе, когда отслеживают изменения цены акции (прибыль/убыток): максимальный подмассив соответствует «лучшему окну» для покупки и продажи. Аналогично её используют при анализе температурных рядов или сейсмических данных — чтобы найти интервалы, где условия устойчиво «хорошие» или «плохие».

Пример: для массива $[2, -1, 3, 4, 1, -5]$ подмассив $[-1, 3, 4, 1]$ (с индекса 2 по 5) имеет сумму 7, и это максимум.

1.4.2 Наивный перебор (brute force)

Прямолинейный алгоритм проверяет каждый возможный подмассив:

for l = 1 to n
  for r = l to n
    вычислить сумму A[l...r] в sum
    если sum > best_sum:
      best_sum = sum
      best_l = l
      best_r = r

Внутренние циклы перебирают все $\binom{n+1}{2} = \Theta(n^2)$ подмассивов. Даже при оптимизации (накапливая суммы по шагам) в лучшем случае остаётся $\Theta(n^2)$, что для больших $n$ медленно.

1.4.3 Решение divide and conquer

Ключевая идея: максимальный подмассив в $A[l \dots r]$ лежит ровно в одном из трёх вариантов:

Целиком в левой половине — $A[l \dots m]$, где $m = \lfloor (l + r) / 2 \rfloor$
Целиком в правой половине — $A[m + 1 \dots r]$
Пересекает середину — тянется от какого-то индекса слева до какого-то справа

В случаях 1 и 2 рекурсируем. В случае 3 нужен отдельный приём: рекурсией нельзя «собрать» подмассивы, которые пересекают точку деления.

Пересекающий подмассив находится за линейное время: от середины расширяемся влево и вправо, на каждом шаге отслеживая лучшую сумму. Это $O(n)$ без дополнительной рекурсии.

Структура алгоритма:

FIND-MAXIMUM-SUBARRAY(A, l, r):
  if l == r:
    return (l, r, A[l])  // база: один элемент
  else:
    m = floor((l + r) / 2)
    (left_l, left_r, left_sum) = FIND-MAXIMUM-SUBARRAY(A, l, m)
    (right_l, right_r, right_sum) = FIND-MAXIMUM-SUBARRAY(A, m + 1, r)
    (cross_l, cross_r, cross_sum) = FIND-MAX-CROSSING-SUBARRAY(A, l, m, r)

    // максимум из трёх вариантов
    if left_sum >= right_sum and left_sum >= cross_sum:
      return (left_l, left_r, left_sum)
    else if right_sum >= left_sum and right_sum >= cross_sum:
      return (right_l, right_r, right_sum)
    else:
      return (cross_l, cross_r, cross_sum)

Вспомогательная процедура FIND-MAX-CROSSING-SUBARRAY находит лучший пересекающий подмассив:

FIND-MAX-CROSSING-SUBARRAY(A, l, m, r):
  // лучшая сумма, начиная с m и расширяясь влево
  left_sum = -∞
  sum = 0
  for i = m down to l:
    sum = sum + A[i]
    if sum > left_sum:
      left_sum = sum
      max_left = i

  // лучшая сумма, начиная с m+1 и расширяясь вправо
  right_sum = -∞
  sum = 0
  for j = m + 1 to r:
    sum = sum + A[j]
    if sum > right_sum:
      right_sum = sum
      max_right = j

  return (max_left, max_right, left_sum + right_sum)

Эта процедура работает за $\Theta(n)$: один проход от середины к краям.

1.4.4 Анализ сложности

Рекуррентность: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Divide: $\Theta(1)$ — найти середину
Conquer: два рекурсивных вызова, каждый на $n/2$ элементах
Combine: $\Theta(n)$ — найти пересекающий подмассив

Применяем master theorem: $a = 2$, $b = 2$, $f(n) = \Theta(n)$.

Считаем $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.

Так как $f(n) = \Theta(n^1) = \Theta(n)$, это Case 2 (с $k = 0$): \[T(n) = \Theta(n \log n)\]

Это существенное улучшение по сравнению с наивным перебором $\Theta(n^2)$, особенно при больших $n$.

1.5 Сортировка слиянием (merge sort)

Merge sort — один из ключевых алгоритмов сортировки. Это «чистый» divide and conquer, который показывает, как парадигма даёт эффективные и практичные решения.

1.5.1 Обзор и свойства

Тип: divide and conquer
Время: $\Theta(n \log n)$ — гарантированно в лучшем и худшем случаях
Память: $\Theta(n)$ — нужна дополнительная память для слияния
Устойчивость (stability): стабильна — равные элементы сохраняют относительный порядок
In-place: не in-place — при слиянии нужны временные массивы

Устойчивость важна при сортировке объектов с несколькими полями: например, если записи сотрудников сначала отсортированы по имени, а затем по отделу, стабильная сортировка сохранит внутри одного отдела прежний порядок по имени.

1.5.2 Идея алгоритма

Divide: разрезать массив пополам в середине.
Conquer: рекурсивно отсортировать левую и правую половины.
Combine: слить две отсортированные половины в один отсортированный массив.

Смысл: слияние двух уже отсортированных массивов — простая операция, линейная по суммарному размеру; это сильно быстрее, чем сортировать один несортированный массив «с нуля».

1.5.3 Операция merge (слияние)

Слияние двух отсортированных массивов $L$ и $R$ в отсортированный $A$:

Держим указатели i и j в начале $L$ и $R$.
Сравниваем L[i] и R[j], копируем меньший элемент в $A$ и сдвигаем соответствующий указатель.
Когда один массив исчерпан, дописываем хвост из другого.

Пример: слияние $L = [1, 4, 5, 6, 8]$ и $R = [2, 3, 4, 7, 9]$:

1 и 2: копируем 1 → $A = [1]$
4 и 2: копируем 2 → $A = [1, 2]$
4 и 3: копируем 3 → $A = [1, 2, 3]$
4 и 4: копируем 4 из $L$ (для stability) → $A = [1, 2, 3, 4]$
далее → $A = [1, 2, 3, 4, 4, 5, 6, 7, 8, 9]$

Для устойчивости: при равных L[i] и R[j] всегда берём элемент из левого массива $L$ — так сохраняется исходный относительный порядок.

Время: $\Theta(n)$ при $n = |L| + |R|$, каждый элемент просматривается ровно один раз.

1.5.4 Псевдокод

MERGE-SORT(A, p, r):
  if p >= r:
    return  // 0 или 1 элемент уже «отсортирован»
  q = floor((p + r) / 2)
  MERGE-SORT(A, p, q)        // сортировать левую половину
  MERGE-SORT(A, q + 1, r)    // сортировать правую половину
  MERGE(A, p, q, r)          // слить половины

1.5.5 Анализ сложности

Рекуррентность: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Divide: $\Theta(1)$ — вычислить середину
Conquer: два рекурсивных вызова на половинах размера $n/2$
Combine: $\Theta(n)$ — слияние за линейное время

Master theorem: $a = 2$, $b = 2$, $f(n) = \Theta(n)$.

Так как $n^{\log_2 2} = n$ и $f(n) = \Theta(n)$, это Case 2 (с $k = 0$): \[T(n) = \Theta(n \log n)\]

Память: нужно $\Theta(n)$ дополнительной памяти под временные буферы при слиянии — главный минус по сравнению с in-place сортировками.

1.6 Быстрая сортировка (quicksort)

Quicksort — один из самых распространённых на практике алгоритмов сортировки, хотя худший случай у него неприятен. При удачном выборе pivot среднее время отличное, а дополнительная память невелика.

1.6.1 Обзор и свойства

Тип: divide and conquer
Время: худший случай $\Theta(n^2)$, среднее $\Theta(n \log n)$
Память: $\Theta(\log n)$ под стек рекурсии
Устойчивость: не стабильна — при разбиении равные элементы могут «перепрыгивать»
In-place: да — разбиение переставляет элементы на месте, с минимумом доп. памяти

Популярность quicksort — из сильного среднего случая и скромных требований к памяти. В реализациях часто берут случайный pivot, чтобы ожидаемое время оставалось $\Theta(n \log n)$ даже на «враждебных» входах.

1.6.2 Идея алгоритма

Divide: выбрать pivot и разбить массив на три группы:
- элементы $\le$ pivot
- сам pivot
- элементы $>$ pivot
Conquer: рекурсивно отсортировать левую часть ($\le$ pivot) и правую ($>$ pivot).
Combine: по сути конкатенация — pivot уже на финальной позиции, обе стороны отсортированы, значит весь массив отсортирован.

Смысл: в отличие от merge sort, шаг combine здесь неявный: после рекурсии дополнительной «склейки» не нужно.

1.6.3 Алгоритм разбиения (partition)

Partition — сердце quicksort: переставляет массив так, что все элементы $\le$ выбранного pivot оказываются слева, а все $>$ — справа.

In-place partition:

PARTITION(A, p, r):
  x = A[r]           // pivot — последний элемент
  i = p - 1          // граница низкой части

  for j = p to r - 1:     // все, кроме pivot
    if A[j] <= x:
      i = i + 1
      exchange A[i] with A[j]  // в низкую часть

  exchange A[i + 1] with A[r]  // pivot на финальную позицию
  return i + 1        // индекс pivot

Инварианты на каждом шаге:

$A[p \dots i]$: элементы $\le x$ (низкая часть)
$A[i+1 \dots j-1]$: элементы $> x$ (высокая часть)
$A[j \dots r-1]$: ещё не обработаны
$A[r]$: pivot

Время: $\Theta(n)$ — один проход по элементам.

1.6.4 Псевдокод

QUICKSORT(A, p, r):
  if p < r:
    q = PARTITION(A, p, r)     // partition, индекс pivot
    QUICKSORT(A, p, q - 1)     // сортировать ≤ pivot
    QUICKSORT(A, q + 1, r)     // сортировать > pivot

1.6.5 Худший случай

Худший случай — когда pivot всегда минимальный или максимальный: разбиение сильно перекошено (в одной части $n-1$ элементов, в другой 0).

Рекуррентность: \[T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)\]

Разворачивая: \[T(n) \le T(n-1) + cn \le T(n-2) + c(n-1) + cn \le \dots \le T(0) + c \cdot 2 + c \cdot 3 + \dots + cn\] \[= c \sum_{i=2}^{n} i = c \cdot \frac{n(n+1)}{2} - c = \Theta(n^2)\]

Типичный сценарий: вход уже отсортирован (или в обратном порядке), а pivot всегда первый или последний элемент.

1.6.6 Лучший случай

Лучший случай — когда pivot делит массив почти пополам.

Рекуррентность: \[T(n) = 2 \cdot T(n/2) + \Theta(n)\]

Master theorem: $a = 2$, $b = 2$, $f(n) = \Theta(n)$.

Так как $f(n) = \Theta(n^{\log_2 2})$, это Case 2 (с $k = 0$): \[T(n) = \Theta(n \log n)\]

1.6.7 Средний случай

Со случайным pivot (или эвристикой вроде «median of three») разбиения обычно «разумные». Формальный анализ показывает: даже при несбалансированных частях ожидаемое время остаётся $\Theta(n \log n)$.

Наглядно: даже если в одной части четверть элементов, а в другой три четверти, суммарные размеры по уровням рекурсии всё равно убывают достаточно быстро, и глубина логарифмическая.

Формально (Cormen et al., 2022, разд. 7.4) для рандомизированного quicksort: \[E[T(n)] = \Theta(n \log n)\]

1.7 Сравнение алгоритмов сортировки

У разных сортировок разные компромиссы:

Алгоритм	Лучший	Средний	Худший	Память	Stable	In-place
Insertion sort	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$	да	да
Merge sort	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n)$	да	нет
Quicksort	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n^2)$	$\Theta(\log n)$	нет	да
Heapsort	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(1)$	нет	да

Как выбирать:

Merge sort: когда нужен худший случай $\Theta(n \log n)$ или критична stability; платите $\Theta(n)$ памяти.
Quicksort: «универсальная» сортировка: сильное среднее и мало памяти; на уже почти отсортированных данных без рандомизации pivot осторожнее.
Insertion sort: для очень маленьких $n$ (часто $n < 20$) или почти отсортированных массивов — малый накладной расход.
Гибрид: в реальных библиотеках часто quicksort + переход на insertion sort на маленьких подмассивах (типичный порог $n \le 10$).

2. Определения

Алгоритм divide and conquer (divide-and-conquer algorithm): рекурсивный алгоритм, который решает задачу, разбивая её на меньшие независимые подзадачи того же типа, рекурсивно решая каждую (conquer) и объединяя ответы (combine).
Divide: шаг, на котором задача делится на подзадачи, обычно уменьшая размер входа.
Conquer: шаг, на котором подзадачи рекурсивно решаются до base case (подзадача достаточно мала, чтобы решить её напрямую).
Combine: шаг, на котором решения подзадач сливаются в решение исходной задачи.
Рекуррентность (recurrence relation): уравнение, выражающее время $T(n)$ рекурсивного алгоритма через время на меньших размерах; основной инструмент анализа divide and conquer.
Master theorem: прямой способ решать рекуррентности вида $T(n) = a \cdot T(n/b) + f(n)$, сравнивая $f(n)$ с $n^{\log_b a}$.
Case 1 (master theorem): если $f(n) = O(n^{\log_b a - \epsilon})$ при некотором $\epsilon > 0$, доминирует рекурсия и $T(n) = \Theta(n^{\log_b a})$.
Case 2 (master theorem): если $f(n) = \Theta(n^{\log_b a} \log^k n)$ при некотором $k \ge 0$, divide и рекурсия сбалансированы и $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
Case 3 (master theorem): если $f(n) = \Omega(n^{\log_b a + \epsilon})$ при некотором $\epsilon > 0$ и выполнена regularity condition, доминирует divide/combine и $T(n) = \Theta(f(n))$.
Regularity condition: в Case 3 условие $af(n/b) \le c \cdot f(n)$ при некотором $c < 1$; гарантирует «хорошее» поведение ряда стоимостей по уровням рекурсии.
Maximum Subarray Problem: найти непрерывный подмассив максимальной суммы; часто в финансах и временных рядах.
Brute force: алгоритм, систематически перебирающий все варианты; часто неэффективен, но прост для реализации и понимания.
Merge sort: стабильная сортировка divide and conquer с $\Theta(n \log n)$ во всех случаях и дополнительной памятью $\Theta(n)$.
Merge (слияние): операция объединения двух отсортированных массивов в один отсортированный за линейное время.
Stability (устойчивость сортировки): равные элементы сохраняют исходный относительный порядок после сортировки.
Quicksort: in-place сортировка divide and conquer со средним $\Theta(n \log n)$ и худшим $\Theta(n^2)$; на случайных входах часто очень быстра на практике.
Pivot: элемент, вокруг которого в quicksort переставляют массив на «меньше/больше».
Partition: операция quicksort, переставляющая массив так, что элементы $\le$ pivot идут раньше элементов $>$ pivot.
In-place sorting: сортировка без доп. памяти, пропорциональной размеру входа; обычно $O(1)$ или $O(\log n)$ сверху.

3. Формулы

Вид рекуррентности для master theorem: $T(n) = a \cdot T(n/b) + f(n)$ при $a \ge 1$, $b > 1$ и асимптотически неотрицательном $f(n)$
Case 1: если $f(n) = O(n^{\log_b a - \epsilon})$ при некотором $\epsilon > 0$, то $T(n) = \Theta(n^{\log_b a})$
Case 2: если $f(n) = \Theta(n^{\log_b a} \log^k n)$ при некотором $k \ge 0$, то $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$
Case 3: если $f(n) = \Omega(n^{\log_b a + \epsilon})$ при некотором $\epsilon > 0$ и $af(n/b) \le cf(n)$ при $c < 1$, то $T(n) = \Theta(f(n))$
«Масса» рекурсии: $n^{\log_b a} = a^{\log_b n}$ — суммарная работа рекурсивных вызовов по уровням дерева рекурсии
Maximum subarray (divide and conquer): $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$
Maximum subarray (brute force): $T(n) = \Theta(n^2)$ при переборе всех $O(n^2)$ подмассивов
Merge sort: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$
Память merge sort: $\Theta(n)$ дополнительной памяти на слияние
Quicksort (лучший/средний баланс): $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$
Quicksort (худший случай): $T(n) = T(n-1) + \Theta(n) = \Theta(n^2)$
Partition: $\Theta(n)$ на сканирование и перестановки

4. Примеры

4.1. Анализ временной сложности функции обработки связного списка (Набор задач 3, Задание 1)

Найдите худшую временную сложность следующей функции в терминах размера входного связного списка $n$:

/* L — связный список из n элементов */
function process(L)
  if L.is_empty()
    return 0
  else if L.size() == 1
    return L.head.value
  else
    lists = new array of 3 empty linked lists  // три пустых связных списка
    i = 0
    A = L.head
    while A is not None
      if (i mod 4) > 0
        lists[i mod 4].add(A.value)
      A = A.next
      i = i + 1
    result = process(lists[1])
    result += process(lists[2])
    result += process(lists[3])
    return result

(a) Запишите рекуррентное соотношение для $T(n)$.

(b) Найдите асимптотику $T(n)$ методом подстановки, деревом рекурсии или master method. Покажите шаги явно: формальные определения или прямые ссылки на master theorem.

Нажмите, чтобы увидеть решение

Ключевая идея: разобрать структуру функции — сколько элементов попадает в каждую рекурсивную подзадачу, — затем составить и решить рекуррентность.

(a) Рекуррентность

Структура функции:
- База: пустой список и список из одного элемента обрабатываются за $\Theta(1)$
- Рекурсия: один проход по всем $n$ элементам (while), распределение по трём подспискам
- Главный вопрос: сколько элементов в каждом подсписке?
Распределение по подспискам:
- В lists[i mod 4] добавляют только при `(i mod 4) > 0$
- Для $i = 0, 1, 2, \ldots, n-1$:
  - $i \equiv 0 \pmod{4}$: элемент не добавляют
  - $i \equiv 1 \pmod{4}$: в lists[1]
  - $i \equiv 2 \pmod{4}$: в lists[2]
  - $i \equiv 3 \pmod{4}$: в lists[3]
- На каждые 4 подряд идущих элемента распределяются ровно 3 (индексы 1, 2, 3 из 0, 1, 2, 3)
- Всего в три подсписка попадает примерно $3n/4$ элементов
Точнее:
- Если $n = 4k$, распределяется ровно $3k$ элементов — в среднем по $k = n/4$ на список
- Если $n = 4k + r$ при $0 < r < 4$, всего порядка $3n/4$
- В худшем случае размеры близки к $\lceil n/4 \rceil$, $\lceil n/4 \rceil$, $\lceil n/4 \rceil$
Рекуррентность: \[T(n) = \begin{cases} \Theta(1) & \text{if } n \le 1 \\ \Theta(n) + 3T(n/4) & \text{if } n > 1 \end{cases}\]

где $\Theta(n)$ — работа цикла while (проход по $n$ элементам), а $3T(n/4)$ — три рекурсивных вызова на подсписках размера порядка $n/4$.

(b) Асимптотика через master theorem

Параметры:
- $a = 3$ (три рекурсивных вызова)
- $b = 4$ (размер подзадачи порядка $n/4$)
- $f(n) = \Theta(n)$ (нерекурсивная часть — цикл while)
«Масса» рекурсии: \[n^{\log_b a} = n^{\log_4 3} = n^{\log 3 / \log 4} = n^{\approx 0.792}\]

Точнее, $\log_4 3 = \frac{\log 3}{\log 4} = \frac{\ln 3}{\ln 4} \approx 0.7924$
Сравнение $f(n) = \Theta(n)$ с $n^{\log_4 3} = n^{\approx 0.792}$:
- $f(n) = \Theta(n^1)$
- $n^{\log_4 3} = \Theta(n^{0.792})$
- Так как $1 > 0.792$, имеем $f(n) \gg n^{\log_4 3}$ — доминирует $f(n)$
Case 3 master theorem:
- Нужно: $f(n) = \Omega(n^{\log_4 3 + \epsilon})$ при некотором $\epsilon > 0$
- Возьмём $\epsilon = 0.208$, тогда $\log_4 3 + \epsilon = 1$
- Тогда $n = \Omega(n^{1}) = \Omega(n)$ ✓
- Regularity condition: $af(n/b) \le c \cdot f(n)$ при $c < 1$
- $3 \cdot (n/4) = 3n/4$
- Нужно $3n/4 \le c n$ — выполняется при $c = 3/4 < 1$ ✓
Case 3: \[T(n) = \Theta(f(n)) = \Theta(n)\]

Ответ:

(a) $T(n) = 3T(n/4) + \Theta(n)$

(b) По master theorem (Case 3): $T(n) = \Theta(n)$

Несмотря на рекурсию, функция работает за линейное время: на каждом уровне доминирует локальная работа $\Theta(n)$, а подзадачи достаточно быстро сжимаются по размеру.

4.2. Решение рекуррентностей методом master theorem (Набор задач 3, Задание 2)

Решите каждую из рекуррентностей с помощью master theorem. Для каждой укажите, применим ли master method; если да — какой case (1, 2 или 3), явно проверьте условия и дайте ответ в $\Theta$-нотации.

$T(n) = 4T(n/16) + \sqrt{n} \cdot \log_2 n$
$T(n) = 5T(4n/9) + n^2$
$T(n) = 9T(n/4) + \log_2(n!)$
$T(n) = 3T(\sqrt[3]{n}) + n$
$T(n) = \frac{1}{2026}T(2026n) + n\log_{2026}n$

Нажмите, чтобы увидеть решение

(1) $T(n) = 4T(n/16) + \sqrt{n} \cdot \log_2 n$

Параметры: $a = 4$, $b = 16$, $f(n) = \sqrt{n} \cdot \log_2 n = n^{1/2} \log_2 n$
«Масса» рекурсии: \[n^{\log_b a} = n^{\log_{16} 4} = n^{\log_{16} 4}\]

Заметим: $\log_{16} 4 = \frac{\log 4}{\log 16} = \frac{2\log 2}{4\log 2} = \frac{1}{2}$, значит $n^{\log_{16} 4} = n^{1/2} = \sqrt{n}$.
Сравнение с $n^{1/2}$: $f(n) = n^{1/2} \log_2 n = \Theta(n^{1/2} \log^1 n)$ — это Case 2 при $k = 1$.
Case 2 (Cormen et al., Theorem 4.1): $T(n) = \Theta(n^{\log_b a} \log^{k+1} n) = \Theta(\sqrt{n} \log^2 n)$.

Ответ: $T(n) = \Theta(\sqrt{n} \log^2 n)$ (Case 2)

(2) $T(n) = 5T(4n/9) + n^2$

Применимость master theorem: каноническая форма $T(n) = aT(n/b) + f(n)$ предполагает $b > 1$ и размер подзадачи именно $n/b$.
Почему в таком виде «не лезет»: здесь явно $T(4n/9)$; в учебных формулировках master theorem часто требуют запись с константным делителем $b$ в знаменателе аргумента $T(\cdot)$ в стандартном виде; данная запись сразу не совпадает с «шаблоном» из теоремы так же прозрачно, как $T(n/b)$.
Вывод: master method к этой строке не применяют в рамках стандартной проверки; для точного ответа нужны другие приёмы (подстановка, дерево рекурсии).

Ответ: master method неприменим (в смысле стандартной формы из конспекта).

(3) $T(n) = 9T(n/4) + \log_2(n!)$

Упростим $\log_2(n!)$: по Стирлингу $\log(n!) = \Theta(n \log n)$, точнее $\log_2(n!) = \Theta(n \log_2 n)$, то есть $f(n) = \Theta(n \log n)$.
Параметры: $a = 9$, $b = 4$.
«Масса» рекурсии: $n^{\log_4 9}$, где $\log_4 9 = \log_2 3 \approx 1.585$.
Сравнение: $n\log n$ растёт медленнее $n^{1.585}$; при подходящем $\epsilon > 0$ выполняется $f(n) = O(n^{\log_4 9 - \epsilon})$ — это Case 1.
Case 1: $T(n) = \Theta(n^{\log_4 9}) = \Theta(n^{\log_2 3})$.

Ответ: $T(n) = \Theta(n^{\log_2 3})$ (Case 1)

(4) $T(n) = 3T(\sqrt[3]{n}) + n$

Размер подзадачи $n^{1/3}$ — не константное $n/b$ в стандартной форме master theorem.
Замена переменной (идея): $S(m) = T(3^m)$ даёт $S(m) = 3S(m/3) + 3^m$; здесь $f(m) = 3^m$ не полиномиально по $m$ — стандартный master theorem в домене $m$ тоже не подходит.
Вывод: к исходной рекуррентности master method в стандартной форме неприменим.

Ответ: неприменим (размер подзадачи не $n/b$ с константным $b > 1$ в нужном смысле).

(5) $T(n) = \frac{1}{2026}T(2026n) + n\log_{2026}n$

Коэффициент при $T$ меньше 1, размер подзадачи $2026n > n$ — это не $T(n) = aT(n/b) + f(n)$ с $a \ge 1$, $b > 1$.
Такая «рекурсия» не соответствует нормальной модели алгоритма: подзадачи растут, база не достигается.
Вывод: master theorem неприменим, запись некорректна как типичная рекуррентность времени работы.

Ответ: неприменим ($a = \frac{1}{2026} < 1$, подзадачи растут).

4.3. Модифицированный merge sort с insertion sort (Набор задач 3, Задание 3)

Рассмотрите модификацию merge sort: рекурсивное деление останавливается, когда размер подмассива не больше $k$ ($k \le n$). Для подмассива размера $k$ фаза conquer — сортировка insertion sort.

(a) Запишите псевдокод модифицированного алгоритма.

(b) Какова временная сложность в худшем случае (через $n$ и $k$)? Ответ в $\Theta$-нотации с обоснованием.

(c) Какова временная сложность в лучшем случае (через $n$ и $k$)? Ответ в $\Theta$-нотации с обоснованием.

Нажмите, чтобы увидеть решение

(a) Псевдокод

HYBRID-MERGE-SORT(A, p, r, k):
  if r - p + 1 <= k:
    // база: insertion sort на маленьком куске
    INSERTION-SORT(A, p, r)
  else:
    // рекурсия: деление и merge
    q = floor((p + r) / 2)
    HYBRID-MERGE-SORT(A, p, q, k)           // левая половина
    HYBRID-MERGE-SORT(A, q + 1, r, k)      // правая половина
    MERGE(A, p, q, r)                       // слияние

INSERTION-SORT(A, p, r):
  // стандартный insertion sort на A[p..r]
  for i = p + 1 to r:
    key = A[i]
    j = i - 1
    while j >= p and A[j] > key:
      A[j + 1] = A[j]
      j = j - 1
    A[j + 1] = key

(b) Худший случай

Подмассивы длиннее $k$ делятся и сливаются; на размере $\le k$ вызывается insertion sort за $\Theta(k^2)$ в худшем случае.
Глубина деления до «листьев» размера $\le k$: порядка $\log_2(n/k)$; число листьев порядка $n/k$.
Insertion sort: $(n/k)$ вызовов по $\Theta(k^2)$ суммарно дают $\Theta(nk)$.
Слияния: на каждом из $\log_2(n/k)$ уровней суммарно $\Theta(n)$ работы ⇒ $\Theta(n\log(n/k))$.
Итого: \[T_{\text{worst}}(n) = \Theta(nk) + \Theta(n\log(n/k)) = \Theta(nk + n\log(n/k))\]

Так как $\log(n/k) = \log n - \log k$, выражение согласуется с $\Theta(nk + n\log n)$ в типичных оговорках по поглощению членов.

Частные случаи: при $k = O(1)$ получаем $\Theta(n\log n)$; при $k = \Theta(n)$ доминирует $\Theta(n^2)$.

Ответ (b): $T_{\text{worst}}(n, k) = \Theta(nk + n\log(n/k))$ (эквивалентно $\Theta(nk + n(\log n - \log k))$).

(c) Лучший случай

Insertion sort на отсортированном вводе даёт $\Theta(s)$ на подмассив размера $s \le k$ ⇒ на листе $\Theta(k)$, всего $(n/k)\cdot\Theta(k) = \Theta(n)$.
Слияния по-прежнему $\Theta(n)$ на уровень, уровней $\log_2(n/k)$ ⇒ $\Theta(n\log(n/k))$.
Итого: \[T_{\text{best}}(n) = \Theta(n) + \Theta(n\log(n/k)) = \Theta(n\log(n/k))\]

Ответ (c): $T_{\text{best}}(n, k) = \Theta(n\log(n/k))$.

Кратко: худший — $\Theta(nk + n\log(n/k))$; лучший — $\Theta(n\log(n/k))$. Малая константа $k$ (например, 10) даёт практичный гибрид с поведением близким к $\Theta(n\log n)$.

4.4. Решить $T(n) = 2T(n/4) + 1$ через master theorem (Лекция 3, Пример 1)

Решите рекуррентность и дайте асимптотическую оценку.

Нажмите, чтобы увидеть решение

Ключевая идея: выписать $a$, $b$, $f(n)$ и применить подходящий case master theorem.

Параметры: $a = 2$, $b = 4$, $f(n) = 1$ (константная работа divide/combine).
«Масса» рекурсии: $n^{\log_b a} = n^{\log_4 2} = n^{1/2} = \sqrt{n}$.
Сравнение: $f(n) = 1 = O(n^{1/2 - \epsilon})$ при $\epsilon = 1/2$ — Case 1.
Case 1: $T(n) = \Theta(n^{\log_4 2}) = \Theta(\sqrt{n})$.

Ответ: $T(n) = \Theta(\sqrt{n})$

4.5. Решить $T(n) = 2T(n/4) + \sqrt{n}$ через master theorem (Лекция 3, Пример 2)

Нажмите, чтобы увидеть решение

Ключевая идея: если $f(n)$ совпадает с $n^{\log_b a}$ с точностью до логарифмического множителя — Case 2.

Параметры: $a = 2$, $b = 4$, $f(n) = \sqrt{n} = n^{1/2}$.
«Масса» рекурсии: $n^{\log_4 2} = n^{1/2}$.
Сравнение: $f(n) = \Theta(n^{1/2} \log^k n)$ при $k = 0$.
Case 2: $T(n) = \Theta(n^{\log_4 2} \log^{0+1} n) = \Theta(\sqrt{n} \log n)$.

Ответ: $T(n) = \Theta(\sqrt{n} \log n)$

4.6. Решить $T(n) = 2T(n/4) + n$ через master theorem (Лекция 3, Пример 3)

Нажмите, чтобы увидеть решение

Ключевая идея: если $f(n)$ доминирует над $n^{\log_b a}$ и выполнена regularity condition — Case 3.

Параметры: $a = 2$, $b = 4$, $f(n) = n$.
«Масса» рекурсии: $n^{\log_4 2} = \sqrt{n}$.
Сравнение: $f(n) = n$; проверка $f(n) = \Omega(n^{1/2 + \epsilon})$ при $\epsilon = 1/2$ ✓
Regularity condition: $2 \cdot (n/4) \le c n$ при $c = 1/2 < 1$ ✓
Case 3: $T(n) = \Theta(f(n)) = \Theta(n)$.

Ответ: $T(n) = \Theta(n)$

4.7. Трассировка merge sort (Лекция 3, Пример 4)

Отсортируйте массив $[5, 2, 4, 6, 1, 3]$ с помощью merge sort; проследите шаги divide и merge.

Нажмите, чтобы увидеть решение

Ключевая идея: рекурсивно делить пополам, затем сливать уже отсортированные куски.

Исходный массив: $[5, 2, 4, 6, 1, 3]$
Первое деление:
- слева: $[5, 2, 4]$
- справа: $[6, 1, 3]$
Левая половина $[5, 2, 4]$:
- деление: $[5]$ и $[2, 4]$
- дальше $[2, 4]$: $[2]$ и $[4]$
- merge: $[2, 4]$, затем $[5]$ и $[2, 4]$ → $[2, 4, 5]$
Правая половина $[6, 1, 3]$:
- деление: $[6]$ и $[1, 3]$
- дальше $[1, 3]$: $[1]$ и $[3]$
- merge: $[1, 3]$, затем $[6]$ и $[1, 3]$ → $[1, 3, 6]$
Финальный merge:
- слева $[2, 4, 5]$, справа $[1, 3, 6]$
- сравнения дают $[1, 2, 3, 4, 5, 6]$

Ответ: $[1, 2, 3, 4, 5, 6]$

4.8. Трассировка partition в quicksort (Лекция 3, Пример 5)

Выполните partition для массива $[4, 9, 5, 1, 4, 7, 3, 6, 8, 2]$, взяв последний элемент (2) в качестве pivot.

Нажмите, чтобы увидеть решение

Ключевая идея: переставить элементы так, чтобы слева были $\le$ pivot, справа — $>$ pivot.

Исходный массив: $[4, 9, 5, 1, 4, 7, 3, 6, 8, 2]$, pivot $x = 2$ (последний элемент).

Процесс: $i = -1$; $j$ от 0 до 8 (pivot на индексе 9 не трогаем).

Шаг	$j$	$A[j]$	Сравнение	Действие	Массив	$i$
1	0	4	$4 > 2$	пропуск	$[4, 9, 5, 1, 4, 7, 3, 6, 8, 2]$	-1
2	1	9	$9 > 2$	пропуск	$[4, 9, 5, 1, 4, 7, 3, 6, 8, 2]$	-1
3	2	5	$5 > 2$	пропуск	$[4, 9, 5, 1, 4, 7, 3, 6, 8, 2]$	-1
4	3	1	$1 \le 2$	swap $A[0]$ и $A[3]$	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0
5	4	4	$4 > 2$	пропуск	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0
6	5	7	$7 > 2$	пропуск	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0
7	6	3	$3 > 2$	пропуск	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0
8	7	6	$6 > 2$	пропуск	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0
9	8	8	$8 > 2$	пропуск	$[1, 9, 5, 4, 4, 7, 3, 6, 8, 2]$	0

Постановка pivot на место: swap $A[i+1]$ и $A[9]$ (в $A[1]$ было 9) → $[1, 2, 5, 4, 4, 7, 3, 6, 8, 9]$.
Итог: слева от pivot элементы $\le 2$: $[1]$; pivot на индексе 1; справа $[5, 4, 4, 7, 3, 6, 8, 9]$.

Ответ: после partition: $[1, 2, 5, 4, 4, 7, 3, 6, 8, 9]$; pivot на индексе 1.

4.9. Максимальный подмассив методом divide and conquer (Лекция 3, Пример 6)

Найдите максимальный подмассив для $[2, -1, 3, 4, 1, -5]$.

Нажмите, чтобы увидеть решение

Ключевая идея: делим массив, рекурсивно ищем максимум в половинах и отдельно проверяем подмассивы, пересекающие середину.

Массив: $[2, -1, 3, 4, 1, -5]$ (индексы 1–6)
Первое деление при $m = 3$:
- слева: $[2, -1, 3]$
- справа: $[4, 1, -5]$
Левая половина $[2, -1, 3]$:
- деление при $m = 2$: $[2]$ и $[-1, 3]$
- в $[2]$: максимум $[2]$, сумма 2
- в $[-1, 3]$: максимум среди кусков даёт $[3]$ с суммой 3; пересечение даёт сумму 2
- Итог слева: $[3]$, сумма 3
Правая половина $[4, 1, -5]$:
- аналогично получаем максимум справа $[4, 1]$ с суммой 5
Пересечение через исходную середину $m = 3$:
- лучший суффикс слева от индекса 3: сумма 3 (элемент 3)
- лучший префикс справа от индекса 4: $4 + 1 = 5$
- crossing: сумма $3 + 5 = 8$, подмассив $[3, 4, 1]$
Сравнение трёх кандидатов: $3$, $5$, $8$ → глобальный максимум $[3, 4, 1]$ с суммой 8.

Ответ: максимальный подмассив — $[3, 4, 1]$, сумма 8.

4.10. Время работы merge sort (Лекция 3, Пример 7)

Для рекуррентности merge sort $T(n) = 2T(n/2) + \Theta(n)$ найдите решение через master theorem.

Нажмите, чтобы увидеть решение

Ключевая идея: классический Case 2 для merge sort.

Параметры: $a = 2$, $b = 2$, $f(n) = \Theta(n)$ (линейное слияние).
«Масса» рекурсии: $n^{\log_b a} = n$.
Сравнение: $f(n) = \Theta(n^1 \log^k n)$ при $k = 0$.
Case 2: $T(n) = \Theta(n \log n)$.
Смысл: $\Theta(n)$ работы на каждом из $\Theta(\log n)$ уровней дерева рекурсии.

Ответ: $\Theta(n \log n)$.

4.11. Худший случай quicksort (Лекция 3, Пример 8)

Покажите, что quicksort в худшем случае имеет сложность $\Theta(n^2)$, выписав и решив рекуррентность.

Нажмите, чтобы увидеть решение

Ключевая идея: если pivot всегда крайний, разбиение максимально перекошено.

Рекуррентность: $T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + \Theta(n)$.
Развёртка: $T(n) \le T(n-1) + cn \le T(n-2) + c(n-1) + cn \le \cdots$
Сумма: арифметическая прогрессия даёт $\Theta(n^2)$.
Master theorem: здесь не в стандартной форме $b > 1$, но развёртка уже даёт $\Theta(n^2)$.

Ответ: худший случай quicksort — $\Theta(n^2)$.

4.12. Упражнения на master theorem (Лекция 3, Задание 1)

Решите каждую рекуррентность через master theorem; укажите case и обоснуйте.

$T(n) = 3T(n/2) + n^2$
$T(n) = 4T(n/2) + n^2$
$T(n) = T(n/2) + 2^n$
$T(n) = 16T(n/4) + n$

Нажмите, чтобы увидеть решение

(1) $T(n) = 3T(n/2) + n^2$: $n^{\log_2 3} \approx n^{1.585}$; $f(n) = n^2$ доминирует — Case 3 с проверкой regularity ($3/4 < 1$). Ответ: $\Theta(n^2)$.

(2) $T(n) = 4T(n/2) + n^2$: $n^{\log_2 4} = n^2$ — Case 2 при $k = 0$. Ответ: $\Theta(n^2 \log n)$.

(3) $T(n) = T(n/2) + 2^n$: $n^{\log_2 1} = 1$; доминирует $2^n$ — Case 3 (проверка regularity для экспоненты). Ответ: $\Theta(2^n)$.

(4) $T(n) = 16T(n/4) + n$: $n^{\log_4 16} = n^2$; $f(n) = n$ меньше — Case 1. Ответ: $\Theta(n^2)$.

Шаг	\(j\)	\(A[j]\)	Сравнение	Действие	Массив	\(i\)
1	0	4	\(4 > 2\)	пропуск	\([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\)	-1
2	1	9	\(9 > 2\)	пропуск	\([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\)	-1
3	2	5	\(5 > 2\)	пропуск	\([4, 9, 5, 1, 4, 7, 3, 6, 8, 2]\)	-1
4	3	1	\(1 \le 2\)	swap \(A[0]\) и \(A[3]\)	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0
5	4	4	\(4 > 2\)	пропуск	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0
6	5	7	\(7 > 2\)	пропуск	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0
7	6	3	\(3 > 2\)	пропуск	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0
8	7	6	\(6 > 2\)	пропуск	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0
9	8	8	\(8 > 2\)	пропуск	\([1, 9, 5, 4, 4, 7, 3, 6, 8, 2]\)	0

1. Краткое содержание

1.1 Введение в divide and conquer

1.1.1 Три части divide and conquer

1.2 Анализ divide and conquer: рекуррентности

1.2.1 Способы решения рекуррентностей

1.3 Master theorem

1.3.1 Три случая

1.3.2 Смысл \(n^{\log_b a}\)

1.4 Задача о максимальном подмассиве (Maximum Subarray Problem)

1.4.1 Постановка задачи

1.4.2 Наивный перебор (brute force)

1.4.3 Решение divide and conquer

1.4.4 Анализ сложности

1.5 Сортировка слиянием (merge sort)

1.5.1 Обзор и свойства

1.5.2 Идея алгоритма

1.5.3 Операция merge (слияние)

1.5.4 Псевдокод

1.5.5 Анализ сложности

1.6 Быстрая сортировка (quicksort)

1.6.1 Обзор и свойства

1.6.2 Идея алгоритма

1.6.3 Алгоритм разбиения (partition)

1.6.4 Псевдокод

1.6.5 Худший случай

1.6.6 Лучший случай

1.6.7 Средний случай

1.7 Сравнение алгоритмов сортировки

2. Определения

3. Формулы

4. Примеры

4.1. Анализ временной сложности функции обработки связного списка (Набор задач 3, Задание 1)

4.2. Решение рекуррентностей методом master theorem (Набор задач 3, Задание 2)

4.3. Модифицированный merge sort с insertion sort (Набор задач 3, Задание 3)

4.4. Решить \(T(n) = 2T(n/4) + 1\) через master theorem (Лекция 3, Пример 1)

4.5. Решить \(T(n) = 2T(n/4) + \sqrt{n}\) через master theorem (Лекция 3, Пример 2)

4.6. Решить \(T(n) = 2T(n/4) + n\) через master theorem (Лекция 3, Пример 3)

4.7. Трассировка merge sort (Лекция 3, Пример 4)

4.8. Трассировка partition в quicksort (Лекция 3, Пример 5)

4.9. Максимальный подмассив методом divide and conquer (Лекция 3, Пример 6)

4.10. Время работы merge sort (Лекция 3, Пример 7)

4.11. Худший случай quicksort (Лекция 3, Пример 8)

4.12. Упражнения на master theorem (Лекция 3, Задание 1)